A special-purpose processor, like a mathematical processor which serves as a coprocessor of a universal processor and performs mathematical operations, and a network processor which is used for processing network services (switches, routers etc) or the like, is a high-performance processor that is specifically designed for some specific applications.
However, as special applications demand, a special-purpose processor may have to trade some of its flexibility for realization of its specific functions. In general, a special-purpose processor employs a collection of high-performance hardware engines, and each of them is crafted to support specific functions, such as queue management, table lookup, and access to memory or the like. In order to achieve higher performance, a special-purpose processor often adopts a memory structure which departs from the conventional memory hierarchy (e.g., main memory, cache memory or the like). In a special-purpose processor, memory are often partitioned into control memory which houses host information for data processing and data memory which houses data accompanying requests for processing.
In a special-purpose processor which employs at least a search engine, an index table can be implemented for fast lookup. Therefore, there are at least two types of tables supported in such special-purpose processor: index table and flat table. An index table can be implemented as an index tree which is a limited set formed by n (n≧0) nodes and includes a root node, leaf nodes (end nodes) and non-end nodes. Usually, relevant information is stored in leaf nodes. The path from the root node of the index tree to a leaf node is identified by a key in the index table. A user can access an index table by providing a tree ID and a key and then invoking a table lookup (index tree search) command. Latency of a lookup depends on the length of the key and the structure of the tree.
A flat table can be implemented as a memory array. Each row or column of a memory array may store a row (element) of a flat table.
In data processing, data chaining allows data to be well-linked logically, thereby reducing spatial requirements on storage unit while keeping data integrity at the same time. The flexibility of software design of data processing heavily depends on the single pointer as a single and simple mechanism of data chaining.
Due to use for special applications, a special-purpose processor often does not support memory access via a pointer (address of a memory location) and consequently, loses the capability of data chaining via a single pointer. The lack of such a single pointer prevents data chaining from being implemented easily and results in worse flexibility of software design.
Because of upper limit on the size of a leaf node, the capacity of information that can be stored in a leaf node is also restricted. As a result, demands of some complex applications (e.g., tunneling application involved in network communication, or the like) cannot be met. Therefore, there is a need to expand the information capacity of a leaf node, for example.
However, since a special-purpose processor lacks the capability of data chaining via a single pointer, the efficiency of data chaining is rather low, which gives rise to a conflict between large data and small capacity of data storage unit.